package com.onepiece.shipelves.common.myutils.sort;

public class QuickSort {

    //快排是不稳定排序，因为pivot最后会和中区元素交换会导致数字顺序变化如 5 3 3 4 3 6 7 8，5会和第3个3交换
    public static void main(String[] args) {
        int[] nums = {1,2,3,5,2,6,9,3,2,1};
        int[] sortArray = sortArray(nums);
        for (int i = 0; i < sortArray.length; i++) {
            System.out.println(sortArray[i]);
        }

    }

    private static void swap(int[] nums, int i, int j){
        int temp = nums[j];
        nums[j] = nums[i];
        nums[i] = temp;
    }

    private static int[] sortArray(int[] nums) {
        if(nums == null || nums.length == 0)return nums;
        quickSort(nums, 0, nums.length - 1);//right表示最后一个数字
        return nums;
    }

    private static void quickSort(int[] nums, int left, int right) {
        if(left >= right){
            return;
        }
        int q = partition(nums, left, right);
        quickSort(nums, left, q - 1);//中间q排除掉
        quickSort(nums, q + 1, right);
    }

    private static int partition(int[] nums, int left, int right) {
        int pivot = nums[right];
        //让i始终指向比pivot大的数字的第一个位置，这样只要后面还有比pivot小的，就把它替换过去，这样后面只要交换pivot和i指向的数字就好
        int i = left;

        //这里使用-1 是为了少比较一次，自己和自己比没有一定不会小于
        for (int j = left; j <= right - 1; j++) {
            if(nums[j] < pivot){
                swap(nums, i, j);
                i++;
            }
        }
        swap(nums, i, right);
        return i;
    }




}
